class Solution:
	# @param s, a string
	# @param wordDict, a set<string>
	# @return a boolean
	def wordBreak(self, s, wordDict):
		if len(s) < 1:
			return []
		check = [[] for i in xrange(len(s))]
		for i in xrange(len(s)):
			for j in xrange(i-1,-1,-1):
				if len(check[j]) > 0:
					if s[j+1:i+1] in wordDict:
						check[i].append(j)
			if s[:i+1] in wordDict:
				check[i].append(-1)
		print check
		ans = []
		self.__dfs(s, ans, [], check, len(s)-1)
		return ans

	def __dfs(self, s, ans, strList, check, curr):
		if curr == -1:
			anstr = ' '.join(strList)
			ans.append(anstr)
			return
		for begin in check[curr]:
			strList.insert(0, s[begin+1:curr+1])
			self.__dfs(s, ans, strList, check, begin)
			strList.pop(0)


if __name__ == '__main__':
	so = Solution()
	s = 'catsanddog'
	d = set(["cat", "cats", "and", "sand", "dog"])
	import pprint
	pprint.pprint(so.wordBreak(s,d))